package hot100;

import java.util.Deque;
import java.util.LinkedList;

public class Solution42 {

    public int trap(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int leftMax = height[left];
        int rightMax = height[right];
        int sum = 0;
        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if (height[left] > height[right]) {
                sum += rightMax - height[right];
                right--;
            } else {
                sum += leftMax - height[left];
                left++;
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        Solution42 solution42 = new Solution42();
        int[] input = new int[] {0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(solution42.trap(input));
    }

    public int trap1(int[] height) {
        Deque<Integer> stack = new LinkedList<>();
        int sum = 0;
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[stack.peek()] <= height[i]) {
                int min = stack.pop();
                if (!stack.isEmpty() && height[stack.peek()] < height[i]) {
                    sum += (height[stack.peek()] - height[min]) * (min - stack.peek());
                } else if (!stack.isEmpty() && height[stack.peek()] >= height[i]) {
                    sum += (height[i] - height[min]) * (i - min);
                }
            }
            stack.push(i);
        }
        return sum;
    }
}
